package com.nowcoder;

import java.util.Scanner;

/**
 * 王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的。
 * 如果要买归类为附件的物品，必须先买该附件所属的主件，且每件物品只能购买一次。
 * 每个主件可以有 0 个、 1 个或 2 个附件。附件不再有从属于自己的附件。
 * 王强查到了每件物品的价格（都是 10 元的整数倍），而他只有 N 元的预算。除此之外，他给每件物品规定了一个重要度，用整数 1 ~ 5 表示。
 * 他希望在花费不超过 N 元的前提下，使自己的满意度达到最大。
 */
public class ShoppingSatisfaction {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int m = in.nextInt();
        int price[][] = new int[m][3];
        int weight[][] = new int[m][3];
        for (int i = 0; i < m; i++) {
            int v = in.nextInt();
            int p = in.nextInt();
            int q = in.nextInt();
            if (q == 0) {
                price[i][0] = v;
                weight[i][0] = v * p;
            } else {
                if (price[q-1][1] == 0) {
                    price[q - 1][1] = v;
                    weight[q - 1][1] = v * p;
                } else {
                    price[q - 1][2] = v;
                    weight[q - 1][2] = v * p;
                }
            }
        }
        int dp[] = new int[N+1];
        for (int i = 0; i < m; i++) {
            for (int j = N; j >= price[i][0]; j--) {
                if (j >= price[i][0]) {
                    dp[j] = Math.max(dp[j], dp[j-price[i][0]] + weight[i][0]);
                }
                if (j >= price[i][0] + price[i][1]) {
                    dp[j] = Math.max(dp[j], dp[j-price[i][0]-price[i][1]] + weight[i][0] + weight[i][1]);
                }
                if (j >= price[i][0] + price[i][2]) {
                    dp[j] = Math.max(dp[j], dp[j-price[i][0]-price[i][2]] + weight[i][0] + weight[i][2]);
                }
                if (j >= price[i][0] + price[i][1] + price[i][2]) {
                    dp[j] = Math.max(dp[j], dp[j-price[i][0]-price[i][1]-price[i][2]] + weight[i][0] + weight[i][1] + weight[i][2]);
                }
            }
        }
        System.out.println(dp[N]);
    }
}
